#include"heap.h"


void HeapInit(HP* hp)
{
  hp->a = NULL;
  hp->capacity = hp->size = 0;
}

void HeapDestory(HP* hp)
{
  free(hp->a);
  hp->a = NULL;
  hp->capacity = hp->size = 0;
}

void HeapPrint(HP* hp)
{
  int i = 0;
  for(;i<hp->size;i++)
  {
    printf("%d ",hp->a[i]);
  }
  printf("\n");
}

HPDataType HeapTop(HP* hp)
{
  assert(hp);
  return hp->a[0];
}

void swap(HPDataType* x,HPDataType* y)
{
    HPDataType tmp = *x;
    *x = *y;
    *y = tmp;
}

//以大堆为例 
//向下调整
void AdjustDown(int* a,int parent,int n)
{
    assert(a);
    int child = parent*2+1;
    while(child < n)//最坏情况:调整到最后一个叶子节点
    {
        if(child + 1 < n && a[child+1] > a[child] )//选出较大的孩子
        {
          child+=1;
        }
        if(a[child] > a[parent])
        {
            swap(&a[child],&a[parent]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
          break;
        }
    }
}
//向上调整
void AdjustUp(int* a,int child)
{
    assert(a);
    int parent = (child-1)/2;
    while(child > 0) //最坏情况:调整到根节点
    {
        if(a[child] > a[parent])
        {
          swap(&a[child],&a[parent]);
          child = parent;
          parent = (child-1)/2;
        }
        else
        {
          break;
        }
    }
}


void HeapPop(HP* hp)
{
  assert(hp && !HeapEmpty(hp));
  swap(&hp->a[0],&hp->a[hp->size-1]);
  hp->size--;
  AdjustDown(hp->a,0,hp->size);//从0位置向下调整
}

void HeapPush(HP* hp,HPDataType x)
{
    //插入先检查容量
    if(hp->size == hp->capacity)
    {
        int newcapacity = hp->capacity == 0 ? 4:hp->capacity*2;
        HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType)*newcapacity);
        if(tmp == NULL)
        {
            perror("realloc:");
            exit(1);
        }
        hp->a = tmp;
        hp->capacity = newcapacity;
    }
    hp->a[hp->size++] = x;
    AdjustUp(hp->a,hp->size-1);//从最后一个元素child位置向上调整
}

bool HeapEmpty(HP* hp)
{
  assert(hp);
  return hp->size == 0;
}

int HeapSize(HP* hp)
{
    assert(hp);
    return hp->size;
}
